﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace TCPTest
{
    public class Minimax
    {
        private const int INF = 9999;
        private const int NEG_INF = -8888;
        private static SpaceColor[][] board = new SpaceColor[15][];
        List<List<SpaceColor>> tests;
        List<int> nextMoveTheirTestScores;
        List<int> nextMoveMineTestScores;
        private static byte lowX, lowY, highX, highY;
        private SpaceColor myColor, enemyColor;
        private int maxDepth;

        Node originNode;

        public Minimax(Board newBoard, SpaceColor color, int maxDepth)
        {

            this.maxDepth = maxDepth;
            myColor = color;
            enemyColor = opposite(color);
            myColor = SpaceColor.WHITE;
            enemyColor = SpaceColor.BLACK;
            board = newBoard.getBoard();
            initBoundingBox();
            initTestCases();
        }

        public MyMove startAlphaBeta(int depth)
        {
            int alpha = NEG_INF;
            int beta = INF;
            MyMove bestMove = new MyMove(0, 0, SpaceColor.EMPTY);

            for (byte i = lowX; i <= highX; i++)
                for (byte j = lowY; j <= highY; j++)
                    if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                    {
                        MyMove childMove = maxtest(new MyMove(i, j, myColor), depth - 1, alpha, beta);

                        if (alpha < childMove.score)
                        {
                            alpha = childMove.score;
                            bestMove = childMove;
                        }

                        if (beta <= alpha)
                        {
                            i = 15;
                            j = 15;
                            break;
                        }
                    }

            return bestMove;
        }

        public MyMove maxtest(MyMove move, int depth, int alpha, int beta)
        {
            move.doMove();
            if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
            {
                move.score = evaluateBoard(move, depth);
                move.undoMove();
                return move;
            }

            for (byte i = lowX; i <= highX; i++)
                for (byte j = lowY; j <= highY; j++)
                    if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                    {
                        MyMove childMove = mintest(new MyMove(i, j, opposite(move.color)), depth - 1, alpha, beta);
                        alpha = Math.Max(alpha, childMove.score);

                        if (beta <= alpha)
                        {
                            i = 15;
                            j = 15;
                            break;
                        }
                    }
            move.score = alpha;
            move.undoMove();
            return move;
        }

        public MyMove mintest(MyMove move, int depth, int alpha, int beta)
        {
            move.doMove();
            if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
            {
                move.score = evaluateBoard(move, depth);
                move.undoMove();
                return move;
            }

            for (byte i = lowX; i <= highX; i++)
                for (byte j = lowY; j <= highY; j++)
                    if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                    {
                        MyMove childMove = maxtest(new MyMove(i, j, opposite(move.color)), depth - 1, alpha, beta);
                        beta = Math.Min(beta, childMove.score);

                        if (beta <= alpha)
                        {
                            i = 15;
                            j = 15;
                            break;
                        }
                    }
            move.score = beta;
            move.undoMove();
            return move;
        }

        public int adjustScore(int newScore, int depth)
        {
            double nextMoveFactor = 1;
            if ((maxDepth - depth) % 1 == 0)
                nextMoveFactor = .5;

            double depthFactor = (4 + depth);
            depthFactor /= 8;
            return (int)(newScore * depthFactor * nextMoveFactor);
        }

        public int evaluateBoard(MyMove move, int depth)
        {
            int score = 0;

            if (terminatingCondition(myColor))
                return adjustScore(INF, depth);
            if (terminatingCondition(enemyColor))
                return adjustScore(NEG_INF, depth);

            SpaceColor[] row = new SpaceColor[15];
            for (byte x = 0; x < 15; x++) // horizontal
            {
                row = board[x];
                score += scoreRow(row, depth);
            }

            for (byte x = 0; x < 15; x++) // vertical
            {
                row = new SpaceColor[15];
                for (byte y = 0; y < 15; y++)
                    row[y] = board[x][y];
                score += scoreRow(row, depth);
            }

            for (byte x = 0; x < 10; x++) //  Down diag 1
            {
                row = new SpaceColor[15];
                for (byte y = 0; y < 15 - x; y++)
                    row[y] = board[x + y][y];
                score += scoreRow(row, depth);
            }

            for (byte y = 0; y < 10; y++) // Down diag 2
            {
                row = new SpaceColor[15];
                for (byte x = 0; x < 15 - y; x++)
                    row[x] = board[x][y + x];
                score += scoreRow(row, depth);
            }

            for (byte x = 4; x < 15; x++) // Up diag 1
            {
                row = new SpaceColor[15];
                for (byte y = 0; y <= x; y++)
                    row[y] = board[x - y][y];
                score += scoreRow(row, depth);
            }

            for (byte y = 0; y <= 10; y++) // Up diag 2
            {
                row = new SpaceColor[15];
                for (byte x = 0; x < 15 - y; x++)
                    row[x] = board[14 - x][y + x];
                score += scoreRow(row, depth);
            }

            if (score < NEG_INF)
                score = (int)(NEG_INF) + 100;

            if (score > INF)
                score = (int)(INF) - 100;

            return adjustScore(score, depth);
        }

        int scoreRow(SpaceColor[] row, int depth)
        {
            int nonEmptyCount = 0;
            for (int i = 0; i < row.Length; i++)
                if (row[i] != SpaceColor.EMPTY)
                    nonEmptyCount++;

            if (nonEmptyCount == 0)
                return 0;


            for (int testIndex = 0; testIndex < tests.Count; testIndex++)
                for (int i = 0; i <= row.Length - tests[testIndex].Count; i++)
                    for (int j = 0; j < tests[testIndex].Count; j++)
                    {
                        if (row[i + j] == null)
                            break;
                        if (row[i + j] != tests[testIndex][j])
                            break;
                        if (j == tests[testIndex].Count - 1) // Succeeded!
                        {
                            if (maxDepth - depth % 2 == 0)
                                return nextMoveMineTestScores[testIndex];
                            else
                                return nextMoveTheirTestScores[testIndex];
                        }
                    }
            return 0;
        }

        int scoreChains(MyMove move, SpaceColor thisColor, int incrX, int incrY)
        {
            int count = chainCount(move, thisColor, incrX, incrY);
            switch (count)
            {
                case 0: return 0;
                case 1: return 1;
                case 2: return 3;
                case 3: return 12;
                default: return INF;
            }
        }

        int chainCount(MyMove move, SpaceColor myColor, int incrX, int incrY)
        {
            byte x = move.x;
            byte y = move.y;

            int count = 0;

            //first direction (EX: Left)
            while (true)
            {
                x = (byte)(x + incrX);
                y = (byte)(y + incrY);

                if (!legalIndices(x, y) || board[x][y] != myColor)
                    break;

                count++;
            }

            //opposite direction (EX: Right)
            x = move.x;
            y = move.y;
            while (true)
            {
                x = (byte)(x - incrX);
                y = (byte)(y - incrY);

                if (!legalIndices(x, y) || board[x][y] != myColor)
                    break;

                count++;
            }
            return count;
        }
        public bool terminatingCondition(SpaceColor color)
        {
            int count = 0;
            for (byte i = 0; i < 15; i++)
                for (byte j = 0; j < 15; j++)
                {
                    if (board[i][j] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }

            count = 0;
            for (byte i = 0; i < 15; i++)
                for (byte j = 0; j < 15; j++)
                {
                    if (board[j][i] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }

            //Down Diagonals
            for (byte i = 0; i < 11; i++)
                for (byte j = 0; j < (15 - i); j++) // Down diagonals along X axis
                {
                    if (board[i + j][j] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }

            for (byte i = 0; i < 11; i++)
                for (byte j = 0; j < (15 - i); j++) // Down diagonals along Y axis
                {
                    if (board[j][i + j] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }

            //Up Diagonals
            for (byte i = 3; i <= 14; i++)
                for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                {
                    if (board[i - j][j] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }
            for (byte i = 3; i <= 14; i++)
                for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                {
                    if (board[j][i - j] == color)
                        count++;
                    else
                        count = 0;

                    if (count >= 5)
                        return true;
                }

            return false;
        }

        public void initTestCases()
        {
            SpaceColor empty = SpaceColor.EMPTY;

            tests = new List<List<SpaceColor>>();
            nextMoveMineTestScores = new List<int>();
            nextMoveTheirTestScores = new List<int>();

            tests.Add(new List<SpaceColor> { myColor, myColor, myColor, myColor, myColor });
            nextMoveMineTestScores.Add(INF);
            nextMoveTheirTestScores.Add(INF);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, enemyColor, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(NEG_INF);
            nextMoveTheirTestScores.Add(NEG_INF);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor, myColor, myColor, empty });
            nextMoveMineTestScores.Add(9000);
            nextMoveTheirTestScores.Add(9000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor, enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-8000);
            nextMoveTheirTestScores.Add(-8000);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor, myColor, myColor });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(6000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-5000);

            tests.Add(new List<SpaceColor> { myColor, myColor, myColor, myColor, empty });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(6000);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-5000);

            tests.Add(new List<SpaceColor> { myColor, empty, myColor, myColor, myColor });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(3000);
            tests.Add(new List<SpaceColor> { enemyColor, empty, enemyColor, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-2500);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor, myColor, empty });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(6000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-5000);

            tests.Add(new List<SpaceColor> { myColor, myColor, myColor, empty, myColor });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(3000);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, enemyColor, empty, enemyColor });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-2500);

            tests.Add(new List<SpaceColor> { myColor, myColor, empty, myColor, myColor });
            nextMoveMineTestScores.Add(9000);
            nextMoveTheirTestScores.Add(2000);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, empty, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(-8000);
            nextMoveTheirTestScores.Add(-1000);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor, myColor });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(3000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-2000);

            tests.Add(new List<SpaceColor> { myColor, myColor, myColor, empty });
            nextMoveMineTestScores.Add(6000);
            nextMoveTheirTestScores.Add(3000);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-5000);
            nextMoveTheirTestScores.Add(-2000);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor, empty });
            nextMoveMineTestScores.Add(5000);
            nextMoveTheirTestScores.Add(2000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-4000);
            nextMoveTheirTestScores.Add(-1000);

            tests.Add(new List<SpaceColor> { empty, myColor, myColor });
            nextMoveMineTestScores.Add(4000);
            nextMoveTheirTestScores.Add(1000);
            tests.Add(new List<SpaceColor> { empty, enemyColor, enemyColor });
            nextMoveMineTestScores.Add(-3000);
            nextMoveTheirTestScores.Add(-900);

            tests.Add(new List<SpaceColor> { myColor, myColor, empty });
            nextMoveMineTestScores.Add(4000);
            nextMoveTheirTestScores.Add(1000);
            tests.Add(new List<SpaceColor> { enemyColor, enemyColor, empty });
            nextMoveMineTestScores.Add(-3000);
            nextMoveTheirTestScores.Add(-900);

            tests.Add(new List<SpaceColor> { empty, myColor, empty });
            nextMoveMineTestScores.Add(2000);
            nextMoveTheirTestScores.Add(0);
            tests.Add(new List<SpaceColor> { empty, enemyColor, empty });
            nextMoveMineTestScores.Add(-1000);
            nextMoveTheirTestScores.Add(-50);

        }


        public void initBoundingBox()
        {
            for (byte x = 0; x < 15; x++)
                for (byte y = 0; y < 15; y++)
                    updateBoundingBox(x, y);
        }

        public static void updateBoundingBox(byte x, byte y)
        {
            if (board[x][y] != SpaceColor.EMPTY)
            {
                if (x <= lowX)
                {
                    lowX = x;
                    if (x != 0)
                        lowX--;
                }
                if (y <= lowY)
                {
                    lowY = y;
                    if (y > 0)
                        lowY--;
                }
                if (x >= highX)
                {
                    highX = x;
                    if (x < 14)
                        highX++;
                }
                if (y >= highY)
                {
                    highY = y;
                    if (y < 14)
                        highY++;
                }


            }
        }

        public static bool legalIndices(int x, int y)
        {
            return (x >= 0 && x < 15 && y >= 0 && y < 15);
        }


        public Move getBestMove(int depth)
        {
            Console.WriteLine("Starting to evaluate tree");
            MyMove bestMove = startAlphaBeta(depth);

            //Convert back to Move
            return new Move(bestMove.x, bestMove.y, bestMove.color);
        }

        private static SpaceColor opposite(SpaceColor c)
        {
            return (c == SpaceColor.WHITE) ? SpaceColor.BLACK : SpaceColor.WHITE;
        }

        public class MyMove
        {
            public byte x, y;
            public int score;
            public SpaceColor color, prevColor;

            public MyMove(byte x, byte y, SpaceColor color)
            {
                this.x = x;
                this.y = y;
                this.color = color;
                this.score = 0;
            }
            public MyMove(MyMove move)
            {
                this.x = move.x;
                this.y = move.y;
                this.color = move.color;
                this.score = move.score;
            }

            public void doMove()
            {
                prevColor = board[x][y];
                board[x][y] = color;

                updateBoundingBox(x, y);
            }

            public void undoMove()
            {
                board[x][y] = prevColor;
            }
        }

        private class Node
        {
            public MyMove move;
            public int score, depth;

            public List<Node> children;

            public Node(SpaceColor firstColor, int maxDepth) // Only used for Origin Node.
            {
                depth = maxDepth;

                for (byte x = 0; x < 15; x++)
                    for (byte y = 0; y < 15; y++)
                        if (board[x][y] == SpaceColor.EMPTY)
                        {
                            move = new MyMove(x, y, SpaceColor.EMPTY);
                            x = 15;
                            y = 15;
                        }
            }

            public Node(MyMove newMove, int newDepth)
            {
                move = newMove;
                depth = newDepth;
            }

            public void createChildren(SpaceColor childColor)
            {
                children = new List<Node>();

                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                            children.Add(new Node(new MyMove(i, j, childColor), depth - 1));
            }

            public static bool goodSpot(byte x, byte y) //check if there are any close pieces
            {
                int lowXint = (x - 1);
                int lowYint = (y - 1);
                byte lowX = (byte)lowXint;
                byte lowY = (byte)lowYint;
                byte highX = (byte)(x + 1);
                byte highY = (byte)(y + 1);

                if (lowXint < 0) lowX = 0;
                if (lowYint < 0) lowY = 0;
                if (highX > 14) highX = 14;
                if (highY > 14) highY = 14;

                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i][j] != SpaceColor.EMPTY)
                            return true;

                //Didn't find any pieces nearby, probably a trash move.
                return false;
            }

            public bool terminatingCondition(SpaceColor color)
            {
                int count = 0;
                for (byte i = 0; i < 15; i++)
                    for (byte j = 0; j < 15; j++)
                    {
                        if (board[i][j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                count = 0;
                for (byte i = 0; i < 15; i++)
                    for (byte j = 0; j < 15; j++)
                    {
                        if (board[j][i] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                //Down Diagonals
                for (byte i = 0; i < 11; i++)
                    for (byte j = 0; j < (15 - i); j++) // Down diagonals along X axis
                    {
                        if (board[i + j][j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                for (byte i = 0; i < 11; i++)
                    for (byte j = 0; j < (15 - i); j++) // Down diagonals along Y axis
                    {
                        if (board[j][i + j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                //Up Diagonals
                for (byte i = 3; i < 14; i++)
                    for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                    {
                        if (board[i - j][j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }
                for (byte i = 3; i < 14; i++)
                    for (byte j = 0; j <= i; j++) // Up diagonals along X axis
                    {
                        if (board[j][i - j] == color)
                            count++;
                        else
                            count = 0;

                        if (count >= 5)
                            return true;
                    }

                return false;
            }

            /*public void evaluateBoard()
            {
                score = 0;
                SpaceColor myColor = move.color;
                SpaceColor enemyColor = opposite(myColor);

                if (terminatingCondition(myColor))
                {
                    setScore(INF);
                    return;
                }
                if (terminatingCondition(enemyColor))
                {
                    setScore(NEG_INF);
                    return;
                }

                int tempScore = 0;

                for(byte x = 0; x < 15; x++){
                    for (byte y = 0; y < 15; y++)
                    {
                        if(board[x][y] != SpaceColor.EMPTY)
                        {
                            /////// My Score ///////
                            score += scoreChains(move, myColor, 1, 0);  //Horizontal
                            score += scoreChains(move, myColor, 0, 1);  //vertical
                            score += scoreChains(move, myColor, 1, 1);  //UpDiag
                            score += scoreChains(move, myColor, 1, -1); //DownDiag

                            ////// Enemy Score //////
                            score -= scoreChains(move, enemyColor, 1, 0);  //Horizontal
                            score -= scoreChains(move, enemyColor, 0, 1);  //vertical
                            score -= scoreChains(move, enemyColor, 1, 1);  //UpDiag
                            score -= scoreChains(move, enemyColor, 1, -1); //DownDiag
                        }
                    }
                }
                if (score <= NEG_INF)
                    setScore(NEG_INF);
                else if (score >= INF)
                    setScore(INF);
                else
                    setScore(score);
            }*/

            /*public MyMove maxtest(MyMove move, int alpha, int beta)
            {
                move.doMove();
                if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
                {
                    evaluateBoard();
                    move.undoMove();
                    return;
                }
                children = new List<Node>();
                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                        {
                            Node child = new Node(new MyMove(i, j, opposite(move.color)), depth - 1);
                            children.Add(child);

                            child.mintest(alpha, beta);
                            alpha = Math.Max(alpha, child.getScore());

                            if (beta <= alpha)
                                break;

                        }
                score = alpha;
                move.undoMove();
            }

            public MyMove mintest(MyMove move, int alpha, int beta)
            {
                move.doMove();
                if (depth == 0 || terminatingCondition(SpaceColor.WHITE) || terminatingCondition(SpaceColor.BLACK))
                {
                    evaluateBoard();
                    move.undoMove();
                    return;
                }

                children = new List<Node>();
                for (byte i = lowX; i <= highX; i++)
                    for (byte j = lowY; j <= highY; j++)
                        if (board[i][j] == SpaceColor.EMPTY && Node.goodSpot(i, j))
                        {
                            Node child = new Node(new MyMove(i, j, opposite(move.color)), depth - 1);
                            children.Add(child);

                            child.maxtest(alpha, beta);
                            beta = Math.Min(beta, child.getScore());

                            if (beta <= alpha)
                                break;
                        }
                score = beta;
                move.undoMove();
            }*/



            /*
            int scoreChains(MyMove move, SpaceColor myColor, int incrX, int incrY)
            {
                int count = chainCount(move, myColor, incrX, incrY);
                switch (count)
                {
                    case 0: return 0;
                    case 1: return 1;
                    case 2: return 3;
                    case 3: return 12;
                    default: return INF;
                }
            }

            int chainCount(MyMove move, SpaceColor myColor, int incrX, int incrY)
            {
                byte x = move.x;
                byte y = move.y;

                int count = 0;

                //first direction (EX: Left)
                while (true)
                {
                    x = (byte)(x + incrX);
                    y = (byte)(y + incrY);

                    if (!legalIndices(x, y) || board[x][y] != myColor)
                        break;

                    count++;
                }

                //opposite direction (EX: Right)
                x = move.x;
                y = move.y;
                while (true)
                {
                    x = (byte)(x - incrX);
                    y = (byte)(y - incrY);

                    if (!legalIndices(x, y) || board[x][y] != myColor)
                        break;

                    count++;
                }
                return count;
            }
            */
            public void setScore(int newScore)
            {
                double depthFactor = (4 + depth);
                depthFactor /= 8;
                score = (int)(newScore * depthFactor);
            }

            public int getScore()
            {
                return score;
            }
        }
    }
}
